import java.util.ArrayList;

/**
 * Created by forcht on 2018/5/20.
 */
public class Solution {
    public ArrayList<String> generateParenthesis(int n) {
        ArrayList<String> list = new ArrayList<>();
        dfs(list, n, 0, 0, "");
        return list;
    }

    void dfs(ArrayList<String> list, int n, int left, int right, String s) {
        if (right >= n) list.add(s);
        if (left < n)
            dfs(list, n, left + 1, right, s + '(');
        if (right < left)
            dfs(list, n, left, right + 1, s + ')');
    }

    public static void main(String[] args) {
        int[][] a = {{0, 1, 2, 6, 8, 0, 0, 9, 0},
                {6, 0, 0, 0, 0, 4, 0, 1, 0},
                {8, 0, 5, 2, 0, 0, 3, 7, 0},
                {0, 0, 0, 0, 0, 7, 5, 2, 3},
                {0, 0, 0, 4, 0, 6, 0, 0, 0},
                {3, 8, 1, 9, 0, 0, 0, 0, 0},
                {0, 5, 4, 0, 0, 2, 8, 0, 1},
                {0, 7, 0, 3, 0, 0, 0, 0, 2},
                {0, 3, 0, 0, 5, 9, 7, 6, 0}};
        for (int i = 0; i < 9; i++) {
            //填写每个小九宫格
            for (int j = i / 3 * 3, j2 = i / 3 * 3 + 3; j < j2; j++) {
                for (int k = (i % 3) * 3, k2 = (i % 3) * 3 + 3; k < k2; k++) {
                    if (a[j][k] == 0) {
                        for (int t = 1; t <= 9; t++) {
                            //判断小九宫格是否存在该数

                            //判断大九宫格中同列是否存在该数

                            //判断大九宫格中同行是否存在该数

                        }
                    }
                }
            }
        }
    }
}
